package 力扣91;

import java.util.Stack;

/**
 * @ClassName : Day6_768_最多能完成排序的块2
 * @Author : 骆发茂
 * @Date: 2021/12/17 10:45
 * @Description : https://leetcode-cn.com/problems/max-chunks-to-make-sorted-ii/
 * https://leetcode-cn.com/problems/max-chunks-to-make-sorted-ii/solution/768-zui-duo-neng-wan-cheng-pai-xu-de-kua-u059/
 * 可以明确的是每个分块都有一个最大值head，且这些head从左到右递增，
 * 因此只要知道head的数量就知道块的数量，用栈来存储这些head
 * <p>
 * 遍历数组
 * i. 如果当前的数比前一个块的最大值小，也就是比栈顶元素小，并入前一个块
 * 要注意的是如果当前数比倒数第二个块的最大值也要小，前两个块也需要合并，因此这里需要用一个循环
 * ii. 如果当前的数比前一个块的最大值要大，这个数形成一个新的块，把当前的数加入stack中
 * iii. 如果栈为空，当前数直接入栈
 * （情况ii和iii可以合并）
 * <p>
 * 返回栈的长度
 *
 *
 * 首先栈里面总是存的是每一个块里面最大的数  ，最大的数由head保存，while则是用来比较如果当前数比倒数第二个块的最大值也要小，
 * 前两个块也需要合并，因此这里需要用一个循环
 * 因为之前已经stack.pop取出了一个出去，然后while还要继续去stack.peek比较num，也就是比较倒数第二个块的最大值，如果num还要大，说明就要合并在一起
 * 即去掉倒数第二个，由倒数第一个来顶替
 * 例如2，1，3，0，4，4
 * 最后stack是3，4，4
 * 其中2在里面，num==3的时候，stack为2，3
 * 接着num==0，这个时候0《3，
 * head=3，stack为2
 * 0《2
 * 弹出2，即执行stack.pop();//取出
 * 存回3，head
 */
public class Day6_768_最多能完成排序的块2_lc题解 {
    class Solution {
        public int maxChunksToSorted(int[] arr) {
            Stack<Integer> stack = new Stack<>();
            //for循环arr数组找每个数num
            for (int num : arr) {
                //如果栈中不是空的，并且取出的数是要小于栈中的栈顶，也就是外面的要小于栈内的，外面的要小，
                //如果当前的数比前一个块的最大值小，也就是比栈顶元素小，并入前一个块
                if (!stack.empty() && num < stack.peek()) {
                    //可以明确的是每个分块都有一个最大值head，且这些head从左到右递增，
                    //因此只要知道head的数量就知道块的数量，用栈来存储这些head
                    int head = stack.pop();//取出栈顶的，赋予给head，最大值head，栈内最大的head
                    //要注意的是如果当前数比倒数第二个块的最大值也要小，前两个块也需要合并，因此这里需要用一个循环
                    while (!stack.empty() && num < stack.peek()) {
                        stack.pop();//取出
                    }
                    stack.push(head);
                }//如果外面的数是等于或者大于栈内的，//说明这个数形成一个新的块，把当前的数加入stack中
                //或者是第一个数，也存入栈中
                /* * ii. 如果当前的数比前一个块的最大值要大，这个数形成一个新的块，把当前的数加入stack中
                 * iii. 如果栈为空，当前数直接入栈*/
                else {
                    stack.push(num);
                }
            }
            return stack.size();
        }
    }

}